class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]: 
        nums.sort()
        n=len(nums)
        result=[]
        for i in range(n):
            if i>0 and nums[i]==nums[i-1]:
                continue
            if nums[i]>0:
                break
            target=-nums[i]
            k=i+1
            for j in range(n-1,i+1,-1):
                if nums[j]<0:
                    break
                if j<n-1 and nums[j]==nums[j+1]:
                    continue
                while k<j and nums[k]+nums[j]<target:
                    k+=1
                if k==j:
                    break
                if nums[k]+nums[j]==target:
                    result.append([nums[i],nums[k],nums[j]])
                    continue
        return result
                
                
'''
不要过于追求压缩时间复杂度
'''